МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
РОЗРОБЛЕННЯ АЛГОРИТМІВ ТА ПРОГРАМ ДЛЯ АФІННИХ ШИФРІВ. МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 3 З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” Затверджено на засiданнi кафедри “Безпека інформаційних технологій”, протокол № від 2012 р. Львів – 2012  Розроблення алгоритмів та програм для афінних шифрів: Методичні вказівки до лабораторної роботи №3 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 11 с. Укладачі: А.Е.Лагун, к.т.н., доцент А.В.Петришин, асистент Відповідальний за випуск: Л.В. Мороз, к.т.н., доцент. Рецензент: В.М.Максимович, д.т.н., професор. Мета роботи – вивчити математичний апарат для опису афінних шифрів та розробити програмне забезпечення для реалізації афінних шифрів. 1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Афінні шифри є підкласом шифрів заміни, що містять як частковий випадок шифр Віженера і шифр перестановки з фіксованим періодом. Шифри простої заміни Моноалфавітні k-грамні шифри заміни є блоковими шифрами з періодом k. Відповідно, шифри простої заміни можна трактувати як блокові шифри з періодом 1. Опишемо шифр зсуву із застосуванням математичного апарату. n-символьний алфавіт утотожнюємо з кільцем Zn. А саме, кожна буква замінюється своїм номером у алфавіті, причому нумерація починається з нуля. Наприклад, латинська абетка утотожнюється із Z26, а українська із Z33. Літера а української абетки трактується як 0, літера б як 1, в як 2 і т.д. Тепер до букв відкритого тексту можна застосовувати операції додавання та множення за відповідним модулем. Надалі п означає кількість букв у алфавіті відкритого тексту. Шифр зсуву. Ключ: s таке, що
. Шифрування. У повідомленні кожна буква х заміщується буквою E(x)=(x+s) mod n. Розшифрування. У криптотексті кожна буква х' заміщується буквою D(x’)=(x’+s’) mod n, де s’=n-s. Величина зворотного зсуву s' називається розшифровуючим ключем. Лінійний шифр. Ключ: а таке, що 0<a<n і НСД(a,n)=1. Шифрування. У повідомленні кожна буква х заміщується буквою E(x)=(ax) mod n. Розшифрування. У криптотексті кожна буква х' заміщується буквою D(x’)=(a’x’) mod n, де a’=a-1 mod n - розшифровуючий ключ. Нехай повідомлення записуються українською абеткою без пропусків між словами та розділових знаків, тобто п=33. Для шифрування використовується ключ а=5. За допомогою розширеного алгоритму Евкліда знаходимо, що а'=20. Розглянемо процедуру шифрування повідомлення місто. У цифровій формі воно представляється послідовністю чисел 16, 11, 21, 22, 18. Множення на 5 за модулем 33 дає послідовність 14, 22, 6, 11, 24, яка відповідає криптотекстові ктеіф. Розшифрування відбувається так само, лише із використанням розшифровуючого ключа а' = 20. Узагальненням шифру зсуву і лінійного є Афінний шифр . Ключ: a, s такі, що 0 ≤ s <n, 0 < a < n і НСД(a,n)=1. Шифрування. У повідомленні кожна буква х заміщується буквою E(x)=(ax+s) mod n. Розшифрування. У криптотексті кожна буква х' заміщується буквою D(x’)=(a’x’+s’) mod n, де пара a’=a-1 mod n, і s’=(-a’s) mod n є розшифровуючим ключем. Нехай для шифрування використовується ключ а = 5, s = 11. Один з розшифровуючих ключів було знайдено раніше – а' = 20. Тоді, s’=(-20·11) mod 33 = 11. Для зашифрування повідомлення місто, представляємо його у цифровій формі як послідовність 16, 11, 21, 22, 18. Множення на 5 за модулем 33 було виконано вище. До результату додаємо 11 і отримуємо послідовність 25, 0, 17, 22, 2, яка відповідає криптотексту хантв. Розшифрування криптотексту відбувається з використанням розшифровуючого ключа а' = 20, s' = 11. Афінні шифри вищих порядків. Проведемо розширення монограмних шифрів, розглянутих вище, таким чином, щоб вони оперували з...